Same tree

Time: O(N); Space: O(H); easy

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input: p = {TreeNode} [1,2,3], q = {TreeNode} [1,2,3]

  1         1
 / \       / \
2   3     2   3

Output: True

Example 2:

Input: p = {TreeNode} [1,2], q = {TreeNode} [1,null,2]

  1         1
 /           \
2             2

Output: False

Example 3:

Input: p = {TreeNode} [1,2,1], q = {TreeNode} [1,1,2]

  1         1
 / \       / \
2   1     1   2

Output: False

[1]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: boolean
        """
        if p is None and q is None:
            return True

        if p is not None and q is not None:
            return p.val == q.val \
                   and self.isSameTree(p.left, q.left) \
                   and self.isSameTree(p.right, q.right)

        return False

[2]:

s = Solution1()

p = TreeNode(1)
p.left = TreeNode(2)
p.right = TreeNode(3)
q = TreeNode(1)
q.left = TreeNode(2)
q.right = TreeNode(3)
assert s.isSameTree(p, q) == True

p = TreeNode(1)
p.left = TreeNode(2)
p.right = None
q = TreeNode(1)
q.left = None
q.right = TreeNode(2)
assert s.isSameTree(p, q) == False

p = TreeNode(1)
p.left = TreeNode(2)
p.right = TreeNode(1)
q = TreeNode(1)
q.left = TreeNode(1)
q.right = TreeNode(2)
assert s.isSameTree(p, q) == False